package interview;


import java.util.*;

public class lc98 {
    static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(1);
        System.out.println(isValidBST(root));
    }
    public boolean isValidBST1(TreeNode root) {

         //迭代法遍历二叉树
        if(root == null)
            return true;
        TreeNode pre = null;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(!stack.isEmpty() || cur != null){
            while (cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode node = stack.pop();
            if(pre != null && pre.val >= node.val)
                return false;
            pre = node;
            cur = node.right;
        }

        return true;
    }
    static int pre = Integer.MIN_VALUE;
    public static boolean isValidBST(TreeNode root) {
        //递归法

        if(root == null)
            return true;
        return isTrue(root);

    }
    public static boolean isTrue(TreeNode root){
        if(root == null)
        return true;
        if(!isTrue(root.left))
            return false;
        if( pre >= root.val)
            return false;
        pre = root.val;
        return isTrue(root.right);

    }

}
